package cn.good.yan.sf.t6;

import java.util.Iterator;

/**
 * 6 双端队列 - 基于 环形数组的队列
 *
 * @author shengren.yan
 * @create 2024-08-03
 */
public class ArrayDQueue<E> implements DQueue<E>, Iterable<E> {

    E[] arr;
    private int head;
    private int tail;

    @SuppressWarnings("all")
    public ArrayDQueue(int num) {
        arr = (E[]) new Object[num + 1];
    }

    // +法
    private int iec(int i) {
        if (i + 1 >= arr.length) {
            return 0;
        }
        return i + 1;
    }

    // -法
    private int dec(int i) {
        if (i - 1 < 0) {
            return arr.length - 1;
        }
        return i - 1;
    }

    // h
    // t
    // 0 1 2 3 4
    @Override
    public boolean offerFirst(E e) {
        if (isFull()) {
            return false;
        }
        head = dec(head);
        arr[head] = e;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if (isFull()) {
            return false;
        }
        arr[tail] = e;
        tail = iec(tail);
        return true;
    }

    @Override
    public E poolFirst() {
        if (isEmpty()) {
            return null;
        }
        E e = arr[head];
        arr[head] = null;
        head = iec(head);
        return e;
    }


    @Override
    public E poolLast() {
        if (isEmpty()) {
            return null;
        }
        tail = dec(tail);
        E e = arr[tail];
        arr[tail] = null;
        return e;
    }

    @Override
    public E peekFirst() {
        if (isEmpty()) {
            return null;
        }
        E e = arr[head];
        return e;
    }

    @Override
    public E peekLast() {
        if (isEmpty()) {
            return null;
        }
        E e = arr[dec(tail)];
        return e;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    //    h
    // t
    // 0 1 2 3 4
    @Override
    public boolean isFull() {
        if (head > tail) {
            return head - tail == 1;
        } else if (head < tail) {
            return tail - head == arr.length - 1;
        } else {
            return false;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int n = head;

            @Override
            public boolean hasNext() {
                return n != tail;
            }

            @Override
            public E next() {
                E e = arr[n];
                n = iec(n);
                return e;
            }
        };
    }

    public static void main(String[] args) {
        ArrayDQueue<Integer> q = new ArrayDQueue<>(5);
        System.out.println("移除头元素：" + q.poolFirst());
        System.out.println("移除尾元素：" + q.poolLast());
        System.out.println("获取头元素：" + q.peekFirst());
        System.out.println("获取尾元素：" + q.peekLast());
        System.out.println("添加头元素：" + q.offerFirst(1));   // 添加头元素  1
        System.out.println("添加头元素：" + q.offerFirst(2));   // 添加头元素  2 1
        System.out.println("添加头元素：" + q.offerFirst(3));   // 添加头元素  3 2 1
        System.out.println("添加头元素：" + q.offerFirst(4));
        System.out.println("添加头元素：" + q.offerFirst(5));
        System.out.println("添加头元素：" + q.offerFirst(6));
        System.out.println("添加头元素：" + q.offerFirst(7));
        System.out.println("--------------");
        for (Integer i : q) {
            System.out.println(i);
        }
        System.out.println("--------------");
        System.out.println("获取头元素：" + q.peekFirst());
        System.out.println("获取尾元素：" + q.peekLast());
        System.out.println("移除头元素：" + q.poolFirst());
        System.out.println("移除头元素：" + q.poolFirst());
        System.out.println("移除尾元素：" + q.poolLast());
        System.out.println("移除尾元素：" + q.poolLast());
        System.out.println("获取头元素：" + q.peekFirst());
        System.out.println("获取尾元素：" + q.peekLast());
        System.out.println("--------------");
        for (Integer i : q) {
            System.out.println(i);
        }
        System.out.println("--------------");
        System.out.println("添加尾元素：" + q.offerLast(20));   // 尾部添加  3 20
        System.out.println("添加尾元素：" + q.offerLast(30));   // 尾部添加  3 20 30
        System.out.println("添加尾元素：" + q.offerLast(40));
        System.out.println("获取头元素：" + q.peekFirst());
        System.out.println("获取尾元素：" + q.peekLast());
        System.out.println("移除头元素：" + q.poolFirst());
        System.out.println("移除尾元素：" + q.poolLast());
        System.out.println("--------------");
        for (Integer i : q) {
            System.out.println(i);
        }
        System.out.println("--------------");
    }

}
